// https://leetcode.cn/problems/backspace-string-compare/description/

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    bool backspaceCompare(string s, string t) 
    {
        string _s, _t;

        for (const char& ch : s)
        {
            if (ch == '#' && !_s.empty())
                _s.pop_back();
            else 
                if (ch != '#')
                    _s.push_back(ch);
        }

        for (const char& ch : t)
        {
            if (ch == '#' && !_t.empty())
                _t.pop_back();
            else 
                if (ch != '#')
                    _t.push_back(ch);
        }       

        return _s == _t; 
    }
};

int main()
{
    string s11 = "ab#c", s12 = "ad#c";
    string s21 = "ab##", s22 = "c#d#";
    Solution sol;

    cout << sol.backspaceCompare(s11, s12) << endl;
    cout << sol.backspaceCompare(s21, s22) << endl;

    return 0;
}